



<HTML>

<HEAD>

<LINK rel="stylesheet" href="../exer.css">

</HEAD>

<BODY>

<H1>

Data Structures, Algorithms, & Applications in C++<BR>

Chapter 13, Exercise 19<BR>

<BR>

</H1>



<dl compact>

<dt> (a)

<dd>

The algorithm of Figure 13.7 keeps selecting vertices from

<em class=var>A</em>

until we either have a cover or all vertices of

<em class=var>A</em> have been included in the cover

<em class=var>A'</em> that is being constructed.

Therefore, when the algorithm terminates without a cover,

<em class=var>A'</em> =

<em class=var>A</em> and

<em class=var>A</em> does not cover all vertices of

<em class=var>B</em>.  So the given bipartite graph

has no cover.

<br><br>

<dt> (b)

<dd>

Consider the 9 vertex bipartite graph with

<em class=var>A</em> = {1, 2, 3};

<em class=var>B</em> = {4, 5, 6, 7, 8, 9};

and edges {(1,4), (1,5), (1,6), (1,7), (2,6), (2,7), (2,8), (3,4), (3,5),

(3,9)}.  The cover constructed by the greedy algorithm of Figure 13.7

is {1, 2, 3}.  The minimum cover is {2, 3}.





</FONT>

</BODY>

</HTML>

